package com.tau.egonetwork.algorithms;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;

import edu.uci.ics.jung.algorithms.metrics.Metrics;
import edu.uci.ics.jung.graph.util.EdgeType;

public class GraphUtils {

	public static <T> Map<T, Double> clusteringCoefficients(EgoNetworkGraph<T> graph) {
		return Metrics.clusteringCoefficients(graph);
	}
	
	public static <T> Map<T, Double> clusteringCoefficientsNoRoot(EgoNetworkGraph<T> graph, T root) {
		EgoNetworkGraph<T> copy = copyGraph(graph);
		copy.removeVertex(root);
		return Metrics.clusteringCoefficients(copy);
	}
	
	public static <T> EgoNetworkGraph<T> copyGraph(EgoNetworkGraph<T> graph) {
		
		EgoNetworkGraph<T> copy = new EgoNetworkGraph<T>();
		
		for (T t : graph.getVertices())
			copy.addVertex(t);
		
		for (int i : graph.getEdges())
			copy.addEdge(i, graph.getIncidentVertices(i), EdgeType.UNDIRECTED);
		
		return copy;
		
	}
	
	public static <T> Map<T, Double> meanShortestPaths(EgoNetworkGraph<T> graph, IShortestPathProgress progress) {
		
		Map<T, Double> shortestPaths = new TreeMap<T, Double>();
		
		//go over all vertices:
		int i = 0;
		for (T t : graph.getVertices()) {
			
			if (progress != null)
				progress.calculting(++i);
			
			/* OLD METHOD (CURRENTLY UNUSED) : works on general graphs,
			 * we improved running time dramatically for specific
			 * egocenteric network graph. This should be used
			 * when not all nodes are necessarily connected to a root.
			
			//for each vertex t, calculate shortest paths to all other vertices:
			DijkstraShortestPath<T, Integer> dijkstra =
					new DijkstraShortestPath<T, Integer>(graph);
			
			//calculate sum of all shortest paths to vertex t:
			int sum = 0;
			int count = 0;
			for (T v : graph.getVertices()) {
				
				if (v.equals(t))
					continue;
				
				Number distance = dijkstra.getDistance(v, t);
				if (distance != null) {					
					sum += distance.intValue();
					count++;
				}
				
			}*/
			
			//go over all graph vertices, if vertex is t's neighbor, then shortest path
			//is 1, otherwise 2 (can always reach via the egocenteric node):
			int sum = 0;
			int count = 0;
			for (T v : graph.getVertices()) {
				
				if (v.equals(t))
					continue;
				
				if (getIncidentVertices(graph, v).contains(t)) {
					sum +=1;
				} else {
					sum +=2;
				}
				count++;
				
			}
						
			//put the average of vertex t in map:
			shortestPaths.put(t, sum / (double)count);
		}
		
		return shortestPaths;
	}
	
	public static <T> Map<T, Integer> kshellDecompositionNoRoot(EgoNetworkGraph<T> graph, T root) {
		EgoNetworkGraph<T> copy = copyGraph(graph);
		copy.removeVertex(root);
		return kshellDecomposition(copy);
	}
	
	public static <T> Map<T, Integer> kshellDecomposition(EgoNetworkGraph<T> graph) {
		
		Map<T, Integer> shells = new TreeMap<T, Integer>();

		//since we'll be removing vertices from the graph, copy to any graph
		//to avoid any changes to the parameter:
		EgoNetworkGraph<T> copyGraph = copyGraph(graph);
		
		int k = 1;
		
		while (copyGraph.getVertexCount() > 0) {
						
			ArrayList<T> verticesWithK = new ArrayList<T>();
			ArrayList<T> verticesLessThanK = new ArrayList<T>();
			
			for (T v : copyGraph.getVertices()) {
				if (copyGraph.degree(v) == k) {
					verticesWithK.add(v);
				} else if (copyGraph.degree(v) < k) {
					verticesLessThanK.add(v);
				}
			}
			
			if (verticesWithK.size() == 0 && verticesLessThanK.size() == 0) {
				k++;
			} else {
				for (T v : verticesWithK) {
					copyGraph.removeVertex(v);
					shells.put(v, k);
				}
				for (T v : verticesLessThanK) {
					copyGraph.removeVertex(v);
					shells.put(v, k+1);
				}
			}

		}
		
		return shells;
		
	}
	
	
	private static <T> Map<T, Integer> clusterWith1(EgoNetworkGraph<T> graph, IClusterProgress progress) {
		
		Map<T, Integer> result = new TreeMap<T, Integer>();
		
		List<T> permutation = permutate(new ArrayList<T>(graph.getVertices()));
		
		if (progress != null)
			progress.start(permutation.size());
		
		int cluster = 0;
		int i = 0;
		while (!permutation.isEmpty()) {

			T vertex = permutation.get(0);
			permutation.remove(0);
			
			if (progress != null)
				progress.progress(++i);

			List<T> incidentVertices = getIncidentVertices(graph, vertex);
			
			Set<T> verticesInCluster = new TreeSet<T>();
			verticesInCluster.add(vertex);
			verticesInCluster.addAll(incidentVertices);
			for (T incidentVertex : incidentVertices) {
				
				List<T> incidentVerticesToIncidentVertex = getIncidentVertices(graph, incidentVertex);
				verticesInCluster.addAll(incidentVerticesToIncidentVertex);
				
			}

			if (verticesInCluster.size() > 1) {
				if (!result.containsKey(vertex)) {
					//increment cluster and add all to it (otherwise this was a subsequent check
					//of a vertex already previously added to a cluster by the same cluster num
					//identification:
					cluster++;
				}
				for (T t : verticesInCluster) {
					result.put(t, cluster);
					//if t was in permutation (scheduled to be randomly chosen later,
					//move it to the front of the permutation so it will be checked
					//next (with the same cluster num identification):
					if (permutation.remove(t))
						permutation.add(0, t);
				}
			}
		}
		
		return result;
	}
	
	public static <T> Map<T, Integer> cluster(EgoNetworkGraph<T> graph, int input, IClusterProgress progress) {

		if (input == 1)
			return clusterWith1(graph, progress);
		
		Map<T, Integer> result = new TreeMap<T, Integer>();
		
		List<T> permutation = permutate(new ArrayList<T>(graph.getVertices()));		
		
		if (progress != null)
			progress.start(permutation.size());

		int cluster = 0;
		int k = 0;
		while (!permutation.isEmpty()) {
			
			T vertex = permutation.get(0);
			permutation.remove(0);
			
			if (progress != null)
				progress.progress(++k);

			if (graph.degree(vertex) < input)
				continue;
			
			List<T> incidentVertices = getIncidentVertices(graph, vertex);
			int numOfIncidentVertices = incidentVertices.size();
			
			Set<T> verticesInCluster = new TreeSet<T>();
			verticesInCluster.add(vertex);
			
			for (int i = 0; i < numOfIncidentVertices - 1; i++) {
				
				T incidentVertex = incidentVertices.get(i);
				List<T> incidentVerticesToIncidentVertex = getIncidentVertices(graph, incidentVertex);
				
				for (int j = i + 1; j < numOfIncidentVertices; j++) {
					
					T nextIncidentVertex = incidentVertices.get(j);
					List<T> incidentVerticesToNextIncidentVertex = getIncidentVertices(graph, nextIncidentVertex);
					
					//now we have two incident vertices to random vertex and their incident vertices lists.
					
					//check that they have input-1 mutual friends (without vertex - first remove it 
					//so as not to count it):
					
					incidentVerticesToIncidentVertex.remove(vertex);
					incidentVerticesToNextIncidentVertex.remove(vertex);
					
					List<T> mutualVertices = getMutualVertices(
							incidentVerticesToIncidentVertex, incidentVerticesToNextIncidentVertex);					
										
					boolean addToCluster = false;
					if (mutualVertices.size() >= (input-1))  {
						addToCluster = true;
					} else {
						//if there are no input-1 mutual friends, check if these two (incidentVertex and nextIncidentVertex)
						//are friends (if one appears in the next's list or vice versa) and there are input-2 mutual friends:
						if (incidentVerticesToIncidentVertex.contains(nextIncidentVertex) && mutualVertices.size() == (input-2)) {
							addToCluster = true;
						}
					}
					
					if (addToCluster) {
						//add everything to the cluster:
						verticesInCluster.add(incidentVertex);
						verticesInCluster.add(nextIncidentVertex);
						verticesInCluster.addAll(mutualVertices);						
					}
					
				}
				
				
			}
			
			if (verticesInCluster.size() > 1) {
				if (!result.containsKey(vertex)) {
					//increment cluster and add all to it (otherwise this was a subsequent check
					//of a vertex already previously added to a cluster by the same cluster num
					//identification:
					cluster++;
				}
				for (T t : verticesInCluster) {
					result.put(t, cluster);
					//if t was in permutation (scheduled to be randomly chosen later,
					//move it to the front of the permutation so it will be checked
					//next (with the same cluster num identification):
					if (permutation.remove(t))
						permutation.add(0, t);
				}
			}
			
		}

		return result;
		
	}
	
	public static <T> Map<T, Integer> clusterNoRoot(EgoNetworkGraph<T> graph, int input, T root, IClusterProgress progress) {
		EgoNetworkGraph<T> copyGraph = copyGraph(graph);
		copyGraph.removeVertex(root);
		return cluster(copyGraph, input, progress);
	}
	
	private static <T> List<T> getMutualVertices(List<T> incidentToA, List<T> incidentToB) {
		
		ArrayList<T> mutualFriends = new ArrayList<T>();
		
		for (T a : incidentToA) {
			if (incidentToB.contains(a))
				mutualFriends.add(a);
		}
		
		return mutualFriends;
		
	}
	
	private static <T> List<T> getIncidentVertices(EgoNetworkGraph<T> graph, T vertex) {
		
		//get incident edges to T:
		Collection<Integer> incidentEdges = graph.getIncidentEdges(vertex);
		
		//build list of incident vertices:
		List<T> incidentVertices = new ArrayList<T>();
		for (int edge : incidentEdges) {
			//each edge has two incident vertices - the original vetrex and the other
			//one, which we are interested in. extract that one.
			Collection<T> verticesOnEdge = graph.getIncidentVertices(edge);
			T t = null;
			for (T tt : verticesOnEdge) {
				if (!tt.equals(vertex)) {
					t = tt;
					break;
				}
			}
			incidentVertices.add(t);
		}

		return incidentVertices;
	}
	
	private static <T> List<T> permutate(List<T> array) {
		
		Random random = new Random();
		
		LinkedList<Float> order = new LinkedList<Float>();
		for (int i = 0; i < array.size(); i++) {
			order.add(new Float(i + random.nextFloat()/2f));
		}
		
		Collections.sort(order, new Comparator<Float> () {
			@Override
			public int compare(Float f1, Float f2) {
				float a = f1.floatValue();
				float b = f2.floatValue();
				
				a -= (float)Math.floor(a);
				b -= (float)Math.floor(b);
				
				if (a > b)
					return -1;
				if (b > a)
					return 1;
				return 0;
			}
		});
		
		List<T> perm = new ArrayList<T>();
		for (int i = 0; i < array.size(); i++) {
			float p = order.get(i);
			p = Math.abs(p);
			perm.add(array.get((int)p));
		}
		
		return perm;
	}
}